package algorithm.dynamic;

/**
 * leetcode : https://leetcode.com/problems/climbing-stairs/description/
 * Difficulty : Easy
 *
 * 动态规划的思想
 * 从最高层的那个楼梯反推
 *
 * 由于一次只有两种走法，走一层和走两层
 * 那么令 i阶的走法有n(i)种
 * 那么有递推公式： n(i) = n(i-1) + n(i-2)
 * 也就是这两种选择后的结果数量之和
 * 倒数第一阶的走法只有1种，倒数第二阶的走法两种
 * 倒数三=倒数二 + 倒数一
 * 倒数四=倒数三 + 倒数二
 *
 *
 * 进一步优化以后，甚至可以不需要数组
 * @Author Antony
 * @Since 2018/7/14 0:23
 */
public class ClimbingStairs {

    public static void main(String[] args) {
        int s1 = 4;
        int s2 = 3;
        System.out.println(climbStairs(s1));
        System.out.println(climbStairs(s2));
    }

    /**
     * no array
     */
    public static int climbStairs(int n) {
        if(n <= 1){
            return n;
        }
        int pre = 0;
        int cur = 1;
        int tmp;
        while(n > 0){
            tmp = cur;
            cur = cur + pre;
            pre = tmp;
            n--;
        }
        return cur;
    }

    /**
     * beats 100.0% 2ms
     */
    public static int climbStairs_useArray(int n) {
        if(n <= 2){
            return n;
        }
        int[] step = new int[n];
        int index = n-1;
        step[index--] = 1;
        step[index--] = 2;
        while(index >= 0){
            step[index] = step[index+1] + step[index+2];
            index--;
        }

        return step[0];
    }
}
